// https://www.lintcode.com/problem/sum-of-square-numbers/

public class Solution {
    /**
     * @param num: the given number
     * @return: whether whether there're two integers
     */
    public boolean checkSumOfSquareNumbers(int num) {
        // write your code here
        if (num < 0) {
            return false;
        }
        int upper = (int)(Math.sqrt(num));
        for (int i = 0; i <= upper; ++i) {
            int start = i, end = upper;
            while (start <= end) {
                int j = (int)((start + end) / 2);
                int sum = i * i + j * j;
                if (sum == num) {
                    return true;
                } else if (sum > num) {
                    end = j - 1;
                } else {
                    start = j + 1;
                }
            }
        }
        return false;
    }
}